package leetcode.backtrace;

import java.time.temporal.ChronoUnit;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;


/*

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。 

 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
 

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：
    1. 排序后，在dfs时去掉同层相同的数

解法2：
    1. 先将相同的数归到一起做计算，这样重复的就只会被统计一次
    2. 是否使用重复的数x取决于剩余的值 target - x 是否还大于0

 */

public class LeetCode40_CombinationSum2 {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<List<Integer>> result = new ArrayList<>();
        quickSort(candidates, 0, candidates.length - 1);
        solution(result, candidates, target, new ArrayList<>(), new int[1], 0);

        return result;
    }

    public void solution(List<List<Integer>> result, int[] candidates, int target, List<Integer> currentPath, int[] currentValue,
                         int currentIndex){

        if (currentValue[0] == target){
            List<Integer> r = new ArrayList<>(currentPath);
            result.add(r);
            return;
        }
        if (currentValue[0] > target){
            return;
        }
        Set<Integer> usedIndex = new HashSet<>();
        for (int i = currentIndex; i < candidates.length; i++){

            if (usedIndex.contains(candidates[i]))continue;
            usedIndex.add(candidates[i]);

            if (candidates[i] > target){
                continue;
            }
            currentPath.add(candidates[i]);
            currentValue[0] += candidates[i];

            solution(result, candidates, target, currentPath, currentValue, i + 1);

            currentValue[0] -= candidates[i];
            currentPath.remove(currentPath.size() - 1);

        }


    }

    public static void quickSort(int[] cadidates, int startIndex, int endIndex){

        if (startIndex >= endIndex) return;

        int tempStartIndex = startIndex, tempEndIndex = endIndex;
        int pivot = cadidates[startIndex];

        while (tempStartIndex < tempEndIndex){

            while (cadidates[tempEndIndex] > pivot && tempStartIndex < tempEndIndex){tempEndIndex--;}
            if (tempStartIndex == tempEndIndex) break;
            cadidates[tempStartIndex++] = cadidates[tempEndIndex];
            while (cadidates[tempStartIndex] < pivot && tempStartIndex < tempEndIndex){tempStartIndex++;}
            if (tempStartIndex == tempEndIndex) break;
            cadidates[tempEndIndex--] = cadidates[tempStartIndex];

        }

        cadidates[tempStartIndex] = pivot;
        quickSort(cadidates, startIndex, tempStartIndex - 1);
        quickSort(cadidates, tempStartIndex + 1, endIndex);
    }


    public static void main(String[] args) {

//        int[] candidates = new int[]{2, 5, 2, 1, 2};
//        int target = 5;

        int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        List<List<Integer>> lists = new LeetCode40_CombinationSum2().combinationSum2(candidates, target);
        System.out.println("lists = " + lists);

//        quickSort(candidates, 0, candidates.length - 1);
//        System.out.println("candidates = " + candidates);
    }

}
